<?php 
  /**
   * @author claudiugh
   */

require_once('PT_GridPoint.class.php');

define('CLOSE_LIMIT_0', 62000);		// 0.5km
define('CLOSE_LIMIT_1', 100000); 	// 0.8km
define('CLOSE_LIMIT_2', 124000);	// 1km


function xcmp_points($p1, $p2)
{
  return ($p1->x - $p2->x);
}

function ycmp_points($p1, $p2)
{
  return ($p1->y - $p2->y);
}

/**
 * binary search for a point 
 */
function bsearch($points, $p, $cmp)
{
  $l = 0; $r = count($points) - 1;
  while ($l <= $r)
    {
      $m = ($l + $r) >> 1;
      $cmp_res = $cmp($p, $points[$m]); // callback comparison
      if ($cmp_res < 0)
	$r = $m - 1;
      else if ($cmp_res > 0)
	$l = $m + 1;
      else return $m;		// $p == $points[$m]
    }
  return $m;
}

/**
 *
 */
class PT_Grid 
{
  var $points;
  var $ref;

  /**
   * Constructor 
   */
  function PT_Grid()
  {
    $this->points = array();
    //$this->points_y = array(); 
    $this->refx = null;    
    $this->refy = null;    
  }
  
  /**
   * Add a map point (lat, long) to the grid
   */
  function add_map_point($nid, PT_MapPoint $p)
  {
    array_push($this->points, new PT_GridPoint($nid, $p));
    //array_push($this->points_y, new PT_GridPoint($nid, $p));
  }
  
  /**
   * make order in the grid  
   */
  function arrange()
  {
    // sort the points 
    usort($this->points, 'xcmp_points');
    //usort($this->points_y, 'ycmp_points');
  }

  /**
   * 
   */
  function translate($dx, $dy)
  {
    for ($i = 0; $i < count($this->points); $i++)
      $this->points[$i]->translate(-$dx, -$dy);
  }
 

 
  /**
   * @return array of very closed points
   */
  function find_closed_points($D)
  {
    $ret_points = array();
    $n = count($this->points) - 1;
    for ($i = 0; $i < $n; $i++)
      {
	$j = $i + 1;
	while (($j < $n) &&
	       ($this->points[$i]->dx($this->points[$j]) < $D))
	  {
	    if ($this->points[$i]->dy($this->points[$j]) < $D) // apply boundary also on Y 
	      array_push($ret_points,
			 array($this->points[$i]->nid,
			       $this->points[$j]->nid)
			 );
	    $j++;
	  }
      }
    return $ret_points;
  }
  
  /**
   *
   */
  function find_nearby_points($p, $D)
  {
    $ret_points = array();
    $n = count($this->points);
    $i = bsearch($this->points, $p, 'xcmp_points');

    // search forward 
    $j = $i;
    while (($j < $n) && 
      ($p->dx($this->points[$j]) < $D))
      {
	if ($p->dy($this->points[$j]) < $D)
	  array_push($ret_points, $this->points[$j]->nid);
	$j++;
      }
    
    // search backward 
    $j = $i - 1;
    while (($j >= 0) && 
      ($p->dx($this->points[$j]) < $D))
      {
	//echo "$j " . $p->dx($this->points[$j]) . "\n";
	if ($p->dy($this->points[$j]) < $D)
	  array_push($ret_points, $this->points[$j]->nid);
	$j--;
      }

    return $ret_points;
  }

  /**
   * 
   */
  function print_points()
  {
    foreach ($this->points as $p)
      echo $p->to_string() . "\n";
  }
    
}

?>